package com.atguigu.sort;


import java.util.Arrays;

public class MergeSort {

    private MergeSort() {
    }

    public static <E extends Comparable<E>> void Sort(E[] arr) {
        Sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void Sort(E[] arr, int lower, int upper) {
        if (lower >= upper) {
            return;
        }
        int mid = lower + (upper - lower) / 2;//注意越界
        Sort(arr, lower, mid);
        Sort(arr, mid + 1, upper);
        if (arr[mid].compareTo(arr[mid + 1]) >= 0) {
            merge(arr, lower, mid, upper);
        }
    }

    private static <E extends Comparable<E>> void Sort(E[] arr, int lower, int upper, int depth) {
        String depthString = generateDepthString(depth);
        System.out.print(depthString);
        System.out.println(String.format("mergesort arr[%d,%d]", lower, upper));
        if (lower >= upper) {
            return;
        }
        int mid = lower + (upper - lower) / 2;//注意越界
        Sort(arr, lower, mid, depth + 1);
        Sort(arr, mid + 1, upper, depth + 1);

        System.out.print(depthString);
        System.out.println(String.format("merge arr[%d,%d] and arr[%d,%d]", lower, mid, mid + 1, upper));

        merge(arr, lower, mid, upper);

        System.out.print(depthString);
        System.out.print(String.format("after mergeSort arr[%d,%d]：", lower, upper));
        for (E e : arr) {
            System.out.print(e + " ");
        }
        System.out.println();
    }

    private static String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("-");
        }
        return res.toString();
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int lower, int mid, int upper) {
        E[] temp = Arrays.copyOfRange(arr, lower, upper + 1);
        int i = lower, j = mid + 1;
        for (int k = lower; k <= upper; k++) {
            if (i > mid) {
                arr[k] = temp[j - lower];
                j++;
            } else if (j > upper) {
                arr[k] = temp[i - lower];
                i++;
            } else {
                if (temp[i - lower].compareTo(temp[j - lower]) <= 0) {
                    arr[k] = temp[i - lower];
                    i++;
                } else {
                    arr[k] = temp[j - lower];
                    j++;
                }
            }
        }
    }

    //对归并排序进行优化
    public static <E extends Comparable<E>> void Sort2(E[] arr) {
        Sort2(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void Sort2(E[] arr, int lower, int upper) {
        if (upper - lower <= 15) {
            InsertSort.Sort(arr, lower, upper);
            return;
        }
        int mid = lower + (upper - lower) / 2;//注意越界
        Sort2(arr, lower, mid);
        Sort2(arr, mid + 1, upper);
        if (arr[mid].compareTo(arr[mid + 1]) >= 0) {
            merge(arr, lower, mid, upper);
        }
    }

    //内存层面的优化:开辟一次临时空间
    public static <E extends Comparable<E>> void Sort3(E[] arr) {
        E[] temp = Arrays.copyOf(arr, arr.length);
        Sort3(arr, 0, arr.length - 1, temp);
    }

    private static <E extends Comparable<E>> void Sort3(E[] arr, int lower, int upper, E[] temp) {
        if (lower >= upper) {
            return;
        }
        int mid = lower + (upper - lower) / 2;//注意越界
        Sort3(arr, lower, mid, temp);
        Sort3(arr, mid + 1, upper, temp);
        if (arr[mid].compareTo(arr[mid + 1]) >= 0) {
            merge2(arr, lower, mid, upper, temp);
        }
    }

    //自底向下的归并排序算法
    public static <E extends Comparable<E>> void Sort4(E[] arr) {
        E[] temp = Arrays.copyOf(arr, arr.length);
        int n = arr.length;
        for (int size = 1; size < n; size += size) {
            for (int i = 0; i + size < n; i += size + size) {
                if (arr[i + size - 1].compareTo(arr[i + size]) > 0) {
                    merge2(arr, i, i + size - 1, Math.min(i + size + size - 1, n - 1), temp);
                }
            }
        }
    }

    private static <E extends Comparable<E>> void merge2(E[] arr, int lower, int mid, int upper, E[] temp) {
        System.arraycopy(arr, lower, temp, lower, upper - lower + 1);
        int i = lower, j = mid + 1;
        for (int k = lower; k <= upper; k++) {
            if (i > mid) {
                arr[k] = temp[j++];
            } else if (j > upper) {
                arr[k] = temp[i++];
            } else {
                if (temp[i].compareTo(temp[j]) <= 0) {
                    arr[k] = temp[i++];
                } else {
                    arr[k] = temp[j++];
                }
            }
        }
    }

}
